public class CircularSuffixArray
{
	private static final class Comparator1 //implements Comparator<Integer>
	{
		private char[] s;
		private int    len;
		
		public Comparator1(String s)
		{
			this.s   = s.toCharArray();
			this.len = s.length() / 2;
		}
		
		public int compare(int off1, int off2)
		{
			for(int i1 = off1, i2 = off2, e1 = off1 + len; i1 < e1; i1++, i2++) 
			{
				if(s[i1] < s[i2])
					return -1;
				if(s[i1] > s[i2])
					return 1;
			}
			
			return 0;
		}
	}

	private int[] mIndex;
	
    public CircularSuffixArray(String s)  // circular suffix array of s
    {
    	mIndex = new int[s.length()];
    	for(int i = 0; i < mIndex.length; i++)
    		mIndex[i] = i;
    	
    	s = s + s;
    	HeapUtils.sort(mIndex, new Comparator1(s));
    }
    
    public int length()                   // length of s
    {
    	return mIndex.length;
    }
    public int index(int i)               // returns index of ith sorted suffix
    {
    	return mIndex[i];
    }
    
    private static class HeapUtils {
        public static void heapify(int[] array, int size, int pos, Comparator1 cmp) {    
            while (2 * pos + 1 < size) {
                int t = 2 * pos + 1;             
                if (2 * pos + 2 < size && cmp.compare(array[2 * pos + 1], array[2 * pos + 2]) < 0) {
                    t = 2 * pos + 2;
                }
                if (cmp.compare(array[pos], array[t]) < 0) {
                    swap(array, pos, t);
                    pos = t;
                } else {
                    break;
                }
            }
        }


        public static int[] heapMake(int[] array, Comparator1 cmp) {  
            int n = array.length;                   
            for (int i = n - 1; i >= 0; i--) {
                heapify(array, n, i, cmp);
            }
            return array;
        }

        public static void sort(int[] array, Comparator1 cmp) { 
            int n = array.length;
            heapMake(array, cmp);
            while (n > 0) {
                swap(array, 0, n - 1);
                n--;
                heapify(array, n, 0, cmp);
            }
        }

        private static void swap(int[] array, int i, int j) { 
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}
